package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-04-03 13:54
 * @Version 1.0
 **/
public class LongestCommonSubsequence {


    public static void main(String[] args) {

    }

    /**
     * 最长公共子序列的动态规划算法
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int result = 0;
        if (null == text1 || null == text2 || text1.isEmpty() || text2.isEmpty()) {
            return result;
        }
        int len1 = text1.length();
        int len2 = text2.length();
        int dp[][] = new int[len1+1][len2+1];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j]+1;
                } else {
                    dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        result = dp[len1][len2];
        return result;
    }
}
